package hg;

import java.util.Scanner;
import java.util.Arrays;

public class Main1 {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		String Choice;
		String[] str;
		int[] digits=null;
		while(in.hasNextLine())
		{
			Choice=in.nextLine();
			if(Choice.equals("fib"))
			{				
				int n=Integer.parseInt(in.nextLine());
				fib(n);	
			}
			else if(Choice.equals("sort"))
			{
				String line=in.nextLine();
				str=line.split(" ");
				digits=converToIntDigits(str);
				Arrays.sort(digits);
				System.out.println(Arrays.toString(digits));
			}
			else if(Choice.equals("search"))
			{
				Arrays.sort(digits);
				int digit=Integer.parseInt(in.nextLine());
				int pos=Arrays.binarySearch(digits, digit);
				if(pos<0){
					System.out.println(-1);
				}
				else{
					System.out.println(pos);
					}
				}
			 else if(Choice.equals("getBirthDate"))
			{
				int j=Integer.parseInt(in.nextLine());
				for(int i=0;i<j;i++)
				{
					String id=in.nextLine();
					System.out.println(getBirthDate(id));
				}					
			}
			else  System.out.println("exit");
		}
	}

	private static String getBirthDate(String id) {
		String year=id.substring(6,10);
		String month=id.substring(10,12);
		String day=id.substring(12,14);
		return year+"-"+month+"-"+day;
	}

	private static int[] converToIntDigits(String[] str) {
		int[] digits=new int[str.length];
		for(int i=0;i<str.length;i++)
		{
			digits[i]=Integer.parseInt(str[i]);
		}
		return digits;
	}

	private static void fib(int n) {
		int a=1,b=1;
		for(int i=1;i<n;i++)
		{
			System.out.print(a+" ");
			int c=a+b;
			a=b;
			b=c;
			
		}
		System.out.println(a);
	}
}

	